Digital filters are applied to an ever widening range of technology fields. For some applications, adaptive filter coefficients are required, since at least some parameters of the desired processing operation are not known a priori, and/or change over the course of time. For example, wireless communication bandwidth-sharing technologies such as, Frequency Division Multiple Access (FDMA) and Code Division Multiple Access (CDMA) all typically require some sort of digital filtering so as to separate the signals that share a common bandwidth. In many circumstances, the timing synchronicity and/or frequencies of the individual signals are not precisely known, for example due to varying distances to sources and/or Doppler shifts due to moving sources. In these situations it is common to employ an adaptive filter, which uses feedback to refine the values of the filter coefficients, and thereby to optimize the response of the filter.
A variety of algorithms are available for implementation of digital filters. The Least Mean Squares algorithm requires only relatively simple mathematical operations, but has a slow convergence speed and sometimes suffers from so-called “eigenvalues spread.” Compared to least mean squares (LMS) algorithms, recursive least squares (RLS) algorithms have faster convergence speeds and do not exhibit the eigenvalue spread problem. However, RLS algorithms involve more complicated mathematical operations, and require more computational resources than LMS algorithms.
Although digital filters which implement the standard RLS algorithm typically have a fast convergence speed, the standard RLS algorithm diverges when the inverse correlation matrix P(n) loses the properties of positive definiteness and/or Hermitian symmetry. This diverging of the standard RLS algorithm therefore limits its application. However, the QR decomposition-based RLS (QR-RLS) algorithm can resolve this instability. Instead of requiring the computation of the inverse correlation matrix of the input signal, the QR-RLS algorithm works directly with the incoming data matrix through QR decomposition. Therefore, this algorithm guarantees the property of positive definiteness, and is more numerically stable than the standard RLS algorithm.
In some applications of digital filtering, it is necessary to successfully detect and filter weak signals in the presence of one or more very strong signals. One approach is to initially only detect and separate the strong signals, and then to computationally remove the strong signals from the total signal before attempting to isolate and distinguish the weaker signals. However, this approach can introduce significant delay (“latency”) to the process, which can be unacceptable in some real-time applications.
One of the applications to which QR-RLS filters are often applied is to wireless communication. In wireless communication, a variety of modulation schemes can be employed so as to increase the data transmission rate. Among these are BPSK (Binary Phase Shift Keying), QPSK (Quadrature Phase Shift Keying), 4-QAM (4-level Quadrature Amplitude Modulation), and 16-QAM. The optimum modulation scheme depends at least partly upon the signal-to-noise (S/N) of the detected signal. Signals with a high S/N can be modulated using one of the high throughput modulation schemes such as QPSK or 16-QAM. However, signals with lower S/N will experience fewer errors and better overall transmission rates using one of the lower throughput modulation schemes, such as BPSK.
Under circumstances wherein a variety of nodes communicate at different signal strengths, it is desirable to support more than one modulation scheme simultaneously. Typically, communication protocols which support simultaneous use of more than one modulation scheme specify that each packet will include near the beginning of the packet a few modulation identification bits which are transmitted using a default modulation scheme (such as BPSK or QPSK), while the remainder of the packet is transmitted using the specified method (e.g. 16-QAM).
While this can be an efficient approach for maximizing bandwidth usage, errors in reading any of the modulation identification bits can lead to unnecessary packet loss due to inability to read the remainder of the packet, and even to uncertainty as to whether a packet was in fact transmitted.
Another challenge in the application of QR-RLS filters to the communication of wireless signals is the introduction of “impulses” into the signals due to lightening strikes, welding arcs, and other unpredictable EMF noise bursts. Since QR-RLS filters are adaptive, occasional strong signal impulses can cause a filter to “adapt” away from its optimal settings. And the effects of such impulses on QR-RLS performance can be long lasting, since QR-RLS filters typically include a significant number of prior input points when calculating adaptive parameters.
Yet another challenge which arises when wireless signals are asynchronously communicated using the CDMA frequency spreading protocol is that the asynchronous frequency “spreading codes” must be as uncorrelated as possible. Yet it can be very difficult to find asynchronous spreading codes which are substantially uncorrelated for all possible timing offsets.
Still another challenge in wired and wireless communication is the fact that overlapping symbols from various transmitting nodes arrive at the receiver with different timing offsets. Although estimates of the timing offsets are typically known, it can nevertheless be very difficult to select an optimal windowing function which will provide as much signal as possible from each overlapping symbol with a minimum of contribution from neighboring symbols.
Very strong signals with very high S/N can also be a challenge for a QR-RLS filter, since a lack of significant noise can cause divergence of some of the mathematical manipulations included in the QR-RLS algorithm.
A need therefore exists for a QR-RLS adaptive filter which provides fast computation time without requiring excessive computational resources, removes the effects of strong signals so as to enable more reliable detection of weak signals, and avoids divergence of mathematical manipulations due to excessively high S/N. Methods are also needed for reliably detecting modulation schemes without unnecessary loss of packets, removing impulses due to lightening, welding arcs, and other sources so as to avoid adaptation of the filter to these false inputs, finding asynchronous spreading codes with minimum correlations at all timing offsets, and for selecting optimal sampling windows when simultaneously detected symbols include timing offsets due to distance effects and/or other causes.